//
//  445. 两数相加II.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/9/5.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution445 {
    // 可以采用先将两个链表进行反转o(n)
    // 在进行合相加o(n)
    // 题目要求不能对链表进行反转,采用入栈在出栈，弹出时相加即可
    //
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var stack1: [ListNode] = []
        var stack2: [ListNode] = []
        var p1 = l1
        while p1 != nil {
            stack1.append(p1!)
            p1 = p1?.next
        }
        var p2 = l2
        while p2 != nil {
            stack2.append(p2!)
            p2 = p2?.next
        }
        let vHead = ListNode(-1)
        var flag = 0
        while !(stack1.isEmpty && stack2.isEmpty) {
            var sum = flag
            if !stack1.isEmpty {
                sum += stack1.removeLast().val
            }
            if !stack2.isEmpty {
                sum += stack2.removeLast().val
            }
            flag = sum / 10
            let value = sum % 10
            let node = ListNode(value)
            let next = vHead.next
            vHead.next = node
            node.next = next
        }
        if flag == 1 {
            let node = ListNode(1)
            let next = vHead.next
            vHead.next = node
            node.next = next
        }
        return vHead.next
    }
    static func test() {
        let solution = Solution445()
        let result = solution.addTwoNumbers(creatNode1(), createNode2())
        print(result)
    }
    static func creatNode1() -> ListNode? {
        let node7 = ListNode(7)
        let node2 = ListNode(2)
        let node4 = ListNode(4)
        let node3 = ListNode(3)
        node7.next = node2
        node2.next = node4
        node4.next = node3
        return node7
    }
    static func createNode2() -> ListNode? {
        let node5 = ListNode(5)
        let node6 = ListNode(6)
        let node4 = ListNode(4)
        node5.next = node6
        node6.next = node4
        return node5
    }
}
